package array;

public class MergeArray {

    /**
     * 合并两个有序数组，类似于合并两个有序链表，但是如若从头开始会覆盖nums1的原始元素导致错误
     * 思路：将双指针初始化在数组的末尾，然后从后往前合并。
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 两个指针分别初始化在两个数组的最后一个元素（累死拉链两端的锯齿）
        int i = m - 1, j = n - 1;
        // 生成排序的结果（类似拉链的拉锁）
        int p = nums1.length;
        // 从后往前遍历数组，类似合并两个有序链表
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[p] = nums1[i];
                i--;
            } else {
                nums1[p] = nums2[j];
                j--;
            }
            p--;
        }
        // 可能其中一个数组的指针走到尽头了，而另一个还没走完
        // 因为我们本身就是在往 nums1中赋值，所以只需要将nums2的剩余元素赋给nums1即可
        while (j >= 0) {
            nums1[p] = nums2[j];
            j--;
            p--;
        }
    }
}
